#ifndef __LINKTREE_H__
#define __LINKTREE_H__
#include <string>
#include "DynamicArray.hpp"

template <typename T>
class TreeNode
{

public:
    TreeNode(const T &date);

    void Connect(TreeNode<T> *parent);
    // 解绑
    void DisConnect(TreeNode<T> *parent);

    // void show(TreeNode<T> *node, int n);

    static void FreeNode(TreeNode<T> *node);
    static void FindByElement(TreeNode<T> *node, const T &element, DynamicArray<T> &a);
    static int GetNodeHight(TreeNode<T> *node);
    TreeNode<T> *Getparent();
    T &GetDate();

    void SetDate(const T &element)
    {
        date = element;
    }

private:
    T date;                  // 数据域
    TreeNode<T> *parent;     // 双亲指针
    TreeNode<T> *firstchild; // 孩子指针
    TreeNode<T> *nextSbling; // 下一个兄弟指针
};

template <typename T>
class LinkTree
{

public:
    LinkTree()
    {
        root = new TreeNode<T>(T());
    }
    LinkTree(const T &element)
    {
        root = new TreeNode<T>(element);
    }
    ~LinkTree()
    {
        TreeNode<T>::FreeNode(root);
    }
    TreeNode<T> *GetRoot()
    {
        return root;
    }
    // void show();
    DynamicArray<T> FindByElement(const T &element)
    {
        DynamicArray<T> a;
        TreeNode<T>::FindByElement(root, element, a);
        return a;
    }
    int GetTreeHight()
    {
        return TreeNode<T>::GetNodeHight(root) - 1;
    }
    std::string GetNodePath(TreeNode<T> *node)
    {
        if (node == nullptr)
        {
            return std::string();
        }
        std::string path = node->GetDate();
        while (node->Getparent() != nullptr)
        {
            path = node->Getparent()->GetDate() + "/" + path;
            node = node->Getparent();
        }
        return path;
    }

private:
    TreeNode<T> *root; // 根节点
};

template <typename T>
TreeNode<T>::TreeNode(const T &date)
{
    this->data = date;
    parent = firstchild = nextSbling = nullptr;
}

template <typename T>
void TreeNode<T>::Connect(TreeNode<T> *parent)
{
    if (!parent)
        return;
    this->parent = parent;
    // 头插
    this->nextSbling = parent->firstchild;
    parent->firstchild = this;
}

template <typename T>
void TreeNode<T>::DisConnect(TreeNode<T> *parent)
{
    if (parent == nullptr || this->parent != parent)
    {
        return;
    }
    TreeNode<T> *TP = parent->firstchild;
    if (this == parent->firstchild)
    {
        parent->firstchild = this->nextSbling;
    }
    else
    {
        while (TP->nextSbling != nullptr)
        {
            if (TP->nextSbling == this)
            {
                TP->nextSbling = this->nextSbling;

                break;
            }
            TP = TP->nextSbling;
        }
    }

    parent = nextSbling = nullptr;
}

template <typename T>
void TreeNode<T>::FreeNode(TreeNode<T> *node)
{
    if (node == nullptr)
    {
        return;
    }
    FreeNode(node->firstchild);
    FreeNode(node->nextSbling);
    delete node;
}

template <typename T>
void TreeNode<T>::FindByElement(TreeNode<T> *node, const T &element, DynamicArray<T> &a)
{
    if (node == nullptr)
        return;
    if (node->date == element && node->parent != nullptr)
    {
        a.InsertTail(node);
    }
    FindByElement(node->firstchild, element, a);
    FindByElement(node->nextSbling, element, a);
}

template <typename T>
int TreeNode<T>::GetNodeHight(TreeNode<T> *node)
{
    int maxhight = 0;
    if (node == nullptr)
    {
        return 0;
    }
    // 找最高的子树
    TreeNode<T> *TP = node->firstchild;
    while (TP != nullptr)
    {
        int hight = GetNodeHight(TP);
        maxhight = maxhight > hight ? maxhight : hight;
        TP = TP->nextSbling;
    }

    return maxhight + 1;
}

template <typename T>
TreeNode<T> *TreeNode<T>::Getparent()
{
    return parent;
}

template <typename T>
T &TreeNode<T>::GetDate()
{
    return date;
}

#endif
